package com.lihepeng.leecode.solid_aim_offer.linkedlist;

import com.lihepeng.leecode.linkedList.ListNode;

/**
 * 描述
 * 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
 *
 * 数据范围： n \le 1000n≤1000
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 *
 * 例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
 */

public class Solution52 {
    /**
     * inshort 你走我的路，我走你的路，最后咱们相遇了，代表咱们是相同的
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode list1 = pHead1;
        ListNode list2 = pHead2;
        while (list1!=list2) {
            list2 = list2 ==null?list1:list2.next;
            list1 = list1 ==null?list2:list1.next;
        }
        return list1;
    }
}
